Tree এর ধারণা এবং প্রকারভেদ

Tree হলো একটি অপ্রত্যক্ষ ডাটা স্ট্রাকচার যা গাণিতিকভাবে একটি connected acyclic graph হিসাবে সংজ্ঞায়িত করা যায়। একটি ট্রীতে এক বা একাধিক নোড থাকে, এবং প্রতিটি নোডের মধ্যে একটি প্যারেন্ট-চাইল্ড সম্পর্ক থাকে। এটি একটি hierarchical structure, যেখানে একক মূল (root) থেকে শুরু করে বিভিন্ন শাখার (branches) মাধ্যমে ডাটা সংগৃহীত হয়।

Tree এর মৌলিক ধারণা

• Root: একটি গাছের শীর্ষ বা মূল নোড (root node) থেকে অন্যান্য সমস্ত নোডে পৌঁছানো যায়।
• Parent-Child Relationship: প্রতিটি নোডের একটি প্যারেন্ট (parent) নোড থাকতে পারে, এবং সেই প্যারেন্ট নোডের এক বা একাধিক চাইল্ড (child) নোড থাকতে পারে।
• Leaf Node: একটি নোড যা কোন চাইল্ড নোড ধারণ করে না, সেটিকে leaf node বা পাতা নোড বলা হয়।
• Edge: দুইটি নোডের মধ্যে সংযোগ বা সম্পর্ককে edge বলা হয়।
• Subtree: একটি নোড এবং তার সমস্ত চাইল্ড নোডের সমষ্টি একটি subtree তৈরি করে।
• Depth: একটি নোডের depth হলো সেই নোডটি মূল (root) থেকে কতটা দূরে অবস্থিত।
• Height: গাছের উচ্চতা হলো সবচেয়ে গভীর পাতা নোড পর্যন্ত যাওয়ার পথের দৈর্ঘ্য।

Tree এর প্রকারভেদ

Tree বিভিন্ন ধরনের হতে পারে, প্রতিটি ধরনের গাছের নিজস্ব বৈশিষ্ট্য এবং ব্যবহার আছে। নীচে Tree এর কিছু প্রকারভেদ আলোচনা করা হলো:

1. Binary Tree (দ্বৈত গাছ)

একটি Binary Tree হল একটি গাছ যেখানে প্রতিটি নোডে সর্বাধিক দুটি চাইল্ড নোড থাকতে পারে। এই গাছের মধ্যে একক প্যারেন্ট নোড থেকে দুটি চাইল্ড নোডে বিভক্ত করা হয়, এবং প্রতিটি চাইল্ড নোড আবার দুটি নোড ধারণ করতে পারে।

Binary Tree এর প্রকার:

• Full Binary Tree: একটি পূর্ণ দ্বৈত গাছ (Full Binary Tree) হলো এমন একটি গাছ, যেখানে প্রতিটি নোডের ঠিক দুইটি চাইল্ড নোড থাকে (অবশ্যই, leaf nodes এর জন্য দুইটি চাইল্ড থাকতে হবে না)।
• Complete Binary Tree: একটি পূর্ণাঙ্গ দ্বৈত গাছ (Complete Binary Tree) হলো এমন একটি গাছ যেখানে প্রতিটি স্তরের মধ্যে সমস্ত নোড পূর্ণ থাকে, এবং শেষ স্তরের নোডগুলি বাম থেকে ডানে পূর্ণ হয়।
• Perfect Binary Tree: একটি পারফেক্ট দ্বৈত গাছ (Perfect Binary Tree) হলো এমন একটি গাছ যেখানে সমস্ত নোডের মধ্যে সমান সংখ্যা চাইল্ড থাকে এবং সব পাতা একই স্তরে থাকে।

2. Binary Search Tree (BST)

Binary Search Tree (BST) হলো এমন একটি Binary Tree যেখানে প্রতিটি নোডের বাম চাইল্ডে ছোট মান এবং ডান চাইল্ডে বড় মান থাকে। এটি সোজা সোজা অনুসন্ধান এবং ডাটা ইনসার্ট করার জন্য একটি কার্যকরী গাছ।

BST এর বৈশিষ্ট্য:

• একটি BST এর বাম সাবট্রির সব নোডের মান প্যারেন্ট নোডের মান থেকে ছোট হবে।
• একটি BST এর ডান সাবট্রির সব নোডের মান প্যারেন্ট নোডের মান থেকে বড় হবে।
• এটি in-order traversal এ সাজানো ডাটা প্রদান করে।

3. AVL Tree (Adelson-Velsky and Landis Tree)

AVL Tree হলো একটি self-balancing binary search tree (BST), যেখানে গাছের প্রতিটি নোডের জন্য একটি balance factor থাকে। একটি নোডের balance factor হলো তার বাম এবং ডান সাবট্রির উচ্চতার পার্থক্য। যদি এটি 1, 0, বা -1 এর মধ্যে থাকে, তাহলে গাছটি ব্যালেন্সড থাকে। অন্যথায়, রোটেশন প্রয়োগ করে গাছটি ব্যালেন্স করা হয়।

AVL Tree এর বৈশিষ্ট্য:

• এটি সুনির্দিষ্ট সময়ের মধ্যে (O(log n)) সার্চ, ইনসার্ট এবং ডিলিট অপারেশন সম্পন্ন করতে সক্ষম।

4. Red-Black Tree

Red-Black Tree হলো একটি self-balancing binary search tree যা coloring rules ব্যবহার করে গাছের ব্যালেন্স বজায় রাখে। প্রতিটি নোডে একটি রঙ থাকে যা red বা black হতে পারে এবং কিছু নির্দিষ্ট নিয়ম অনুসরণ করা হয় যাতে গাছটি ব্যালেন্সড থাকে। এর মাধ্যমে গাছের অপারেশনগুলি দ্রুত এবং সুনির্দিষ্টভাবে সম্পন্ন করা যায়।

Red-Black Tree এর বৈশিষ্ট্য:

• প্রতিটি নোড red বা black হতে হবে।
• রুট নোডটি always black।
• কোনো red নোডের দুইটি red চাইল্ড থাকতে পারে না।
• প্রতিটি নোড থেকে তার ডাউনস্ট্রীম লিফ পর্যন্ত black height সমান হতে হবে।

5. B Tree

B Tree একটি self-balancing search tree যা sorted ডাটা ধারণ করে এবং balanced থাকে, তাই এটি দ্রুত অনুসন্ধান, ইনসার্ট এবং ডিলিট অপারেশন সম্পন্ন করতে সক্ষম। এটি সাধারণত disk-based storage ব্যবহৃত ডাটাবেসে ব্যবহৃত হয়, যেখানে একটি গাছের উচ্চতা কম রাখতে হয়।

B Tree এর বৈশিষ্ট্য:

• এটি একটি multi-way tree যেখানে প্রতিটি নোডে একটি নির্দিষ্ট সংখ্যক চাইল্ড নোড থাকতে পারে।
• B Tree সাধারণত বৃহত্তর ডাটা স্টোরেজে ব্যবহৃত হয় যেখানে দ্রুত ডাটা ইনসার্ট ও ডিলিট করা প্রয়োজন।

6. Heap Tree

Heap Tree একটি সম্পূর্ণ বাইনারি গাছ (Complete Binary Tree), যেখানে প্রতিটি প্যারেন্ট নোডের মান তার সন্তানের চেয়ে বেশি (max-heap) বা কম (min-heap) থাকে।

Heap Tree এর প্রকার:

• Max Heap: প্রতিটি প্যারেন্ট নোডের মান তার সন্তানের মানের চেয়ে বড় বা সমান।
• Min Heap: প্রতিটি প্যারেন্ট নোডের মান তার সন্তানের মানের চেয়ে ছোট বা সমান।

Heap Tree সাধারণত priority queue এর জন্য ব্যবহৃত হয়, যেখানে সর্বোচ্চ বা সর্বনিম্ন মান বের করা হয় দ্রুত।

7. Trie (Prefix Tree)

Trie একটি বিশেষ ধরনের গাছ যা স্ট্রিং বা শব্দের মধ্যে অগ্রবর্তী অংশ (prefix) সংরক্ষণের জন্য ব্যবহৃত হয়। এটি সাধারণত dictionary বা autocomplete systems এ ব্যবহৃত হয়।

Trie এর বৈশিষ্ট্য:

• এটি একটি multi-way tree যেখানে প্রতিটি নোডে একটি চরিত্র থাকে।
• এটি স্ট্রিং সংরক্ষণ এবং অনুসন্ধানের জন্য কার্যকরী, যেখানে অনুসন্ধান সময় O(m), যেখানে m হল স্ট্রিং এর দৈর্ঘ্য।

সারাংশ

Tree হল একটি অপ্রত্যক্ষ ডাটা স্ট্রাকচার যা একটি হায়ারার্কিক্যাল কাঠামোতে ডাটা সংরক্ষণ করে। Binary Tree, Binary Search Tree (BST), AVL Tree, Red-Black Tree, B Tree, Heap Tree, এবং Trie হল Tree এর বিভিন্ন ধরনের যা বিভিন্ন সমস্যার সমাধান করার জন্য ব্যবহৃত হয়।

• Binary Trees ডাটা সন্নিবেশ এবং অনুসন্ধান দ্রুত করতে সহায়ক।
• AVL Tree এবং Red-Black Tree ব্যালেন্সড গাছ, যেখানে গাছের গঠন সঠিক রাখা হয়।
• Heap গাছগুলি প্রাধান্য বা সর্বাধিক বা সর্বনিম্ন উপাদান অনুসন্ধানের জন্য ব্যবহৃত হয়।
• Trie স্ট্রিং বা শব্দের সাথে সম্পর্কিত সমস্যাগুলির জন্য কার্যকরী।

এই গাছগুলি efficient searching, insertion, deletion এবং sorting অপারেশনগুলির জন্য গুরুত্বপূর্ণ।